1. Field of the Invention
The present invention relates to an image data compression device and, more particularly, to a pattern matching coding device for compressing binary image data by using pattern matching and a method thereof.
2. Description of the Related Art
One of the methods of inputting binary static image by means of a scanner and compressing its bit map data is disclosed in U.S. Pat. No. 5,303,313. According to this method, image data input by a scanner or the like is first compressed by run length coding etc. in advance and then a pattern is cut out therefrom. By the matching between the cut-out pattern and a registered template, generate template data and pattern position data. As a result, the input bit map data is compressed into data composed of a template code and a pattern position.
In order to improve a data compression rate of handwritten characters, unspecified-type characters, etc., proposed is an image data compression device provided with a temporary library allowing new registration or updating of bit map data to be compared with input bit map data according to input data.
FIG. 8 is a block diagram showing one example of a conventional binary static image pattern matching coding device having a temporary updating library. In the figure, image data of a document original input through an original input scanner is subjected to binarization processing and smoothing processing for increasing a compression rate at the time of coding and improving visual image quality. A pattern extraction processing unit 101 extracts a pattern from the data having been subjected to the smoothing processing and outputs bit map data of a mark pattern to a matching processing unit 102. The matching processing unit 102 compares the mark pattern and a bit map pattern preserved in a temporary updating library 103. When a ratio of unmatching pixels to all the pixels is not more than a fixed value, the matching processing unit 102 determines that the patterns match and when the ratio exceeds the fixed value, determines that they unmatch.
When the determination is made at the matching processing unit 102 that the patterns match, output an identification ID of a bit map in the matching temporary updating library and registration data obtained at the time of the matching to a multi-symbol arithmetic coding unit and subjected to data compression. Bit map data of a mark pattern determined to match, after having its match error pixels subjected to inversion processing at a match correction processing unit 104, and bit map data of a mark pattern determined to unmatch, without being subjected to correction processing, are respectively registered as IDs at the temporary updating library 103. At the temporary updating library 103, a library bit map whose matching frequency is low is erased.
At the data compression of bit map data of a mark pattern, for an unmatching mark pattern, a prediction template pixel generated at an unmatching template generation unit is used and for a matching mark pattern, a prediction template pixel generated at a matching template generation unit is used.
The above-described conventional system has problems in image quality and optimization for improving a compression rate because pre-compression processing or smoothing processing is conducted prior to matching processing in order to improve a data compression rate and a temporary library is updated according to data whose match error has been corrected.
In order to solve these problems, Japanese Patent Laying-Open (Kokai) No. Heisei 10-134192 (U.S. Pat. No. 2,940,496) filed by the applicant of the present invention achieves drastic improvement in image quality by using a standard font bit map pattern for matching processing together with bit map data registered at a temporary updating library and proposes making new registration at the temporary updating library only when an input image pattern matches neither a temporary bit map pattern nor a standard font bit map pattern or only when the input image pattern matches only the temporary bit map pattern and is corrected, thereby attaining efficient use of the temporary updating library without wasteful registration. As a result, with a document original etc. printed by a font, a rate of a match with a mark pattern is increased to improve a compression rate. In the illustrated device, arithmetic coding which is well-known art widely used in a device of this kind is used for coding.
In the above-described system, while a compression rate is drastically improved by using a font bit map pattern, bit map data itself of a matching mark pattern is not compressed (no improvement in a compression rate is made in this part). Moreover, arithmetic coding used in pattern coding makes processing complicated and a processing rate lower. For realizing a higher-speed processing device, a component operable at a high-speed should be adopted, which increases costs.
An object of the present invention is to provide a pattern matching coding device realizing highly efficient compression without deteriorating image quality and a method thereof, and further provide a pattern matching coding device enabling coding by simple processing, that is, coding at low costs and at a high speed and a method thereof.
According to the first aspect of the invention, a device for extracting unit patterns from input binary image data and coding the unit patterns based on a result of sequentially conducted pattern matching with a library pattern, comprises
first storage means for storing a first library pattern updatable based on the unit pattern, and
pattern matching means for comparing the unit pattern with the first library pattern to conduct pattern matching processing, wherein
as to a mark pattern determined to be matching, when the number of match error pixels of the pattern is not more than a prescribed value, without coding the bit map, an identification ID of a matching bit map in a library and an identification flag indicating that the number of match error pixels is not more than the prescribed value are coded.
In the preferred construction, the pattern matching coding device further comprises updating control means,
the updating control means, when the unit pattern is determined to match the first library pattern by the pattern matching processing and is not the same as the first library pattern, newly registering the unit pattern at the first storage means.
In another preferred construction, the pattern matching coding device further comprises second storage means for storing a second library pattern of a font designated in advance, wherein
the pattern matching means compares the unit pattern with the first library pattern and second library pattern to conduct pattern matching.
In another preferred construction, the updating control means, furthermore, when the unit pattern is determined to unmatch both the first library pattern and second library pattern by the pattern matching processing, newly registers the unit pattern at the first storage means.
In another preferred construction, in the matching processing, comparison between bit map data of the unit pattern and bit map data of the first library pattern and second library pattern is conducted to determine that the unit pattern is matching when a rate of the number of unmatching pixels of these bit maps is lower than a predetermined value and determine that the unit pattern is unmatching when the rate is higher than the value.
In another preferred construction, the updating control means, furthermore, when the unit pattern is determined to unmatch both the first library pattern and second library pattern by the pattern matching processing, newly registers the unit pattern at the first storage means, and
in the matching processing, comparison between bit map data of the unit pattern and bit map data of the first library pattern and second library pattern is conducted to determine that the unit pattern is matching when a rate of the number of unmatching pixels of these bit maps is lower than a predetermined value and determine that the unit pattern is unmatching when the rate is higher than the value.
In another preferred construction, the pattern matching coding device further comprises
font storage means for storing a plurality of kinds of fonts,
font designating means for designating one of the fonts, and
font development means for developing the designated font into a font bit map to generate the second library pattern.
In another preferred construction, the updating control means, when the unit pattern is determined to unmatch both the first library pattern and second library pattern by the pattern matching processing, newly registers the unit pattern at the first storage means, and which further comprises
font storage means for storing a plurality of kinds of fonts,
font designating means for designating one of the fonts, and
font development means for developing the designated font into a font bit map to generate the second library pattern.
In another preferred construction, in the matching processing, comparison between bit map data of the unit pattern and bit map data of the first library pattern and second library pattern is conducted to determine that the unit pattern is matching when a rate of the number of unmatching pixels of these bit maps is lower than a predetermined value and determine that the unit pattern is unmatching when the rate is higher than the value, and which further comprises
font storage means for storing a plurality of kinds of fonts,
font designating means for designating one of the fonts, and
font development means for developing the designated font into a font bit map to generate the second library pattern.
In another preferred construction, the pattern matching coding device further comprises
font storage means for storing a plurality of kinds of fonts,
font designating means for designating one of the fonts, and
font development means for developing the designated font into a font bit map to generate the second library pattern, wherein
the font designating means detects a font size and a font type from the unit pattern to designate the font.
In another preferred construction, the pattern matching coding device further comprises
font storage means for storing a plurality of kinds of fonts,
font designating means for designating one of the fonts, and
font development means for developing the designated font into a font bit map to generate the second library pattern, wherein
the font designating means is formed of input means for externally designating the font.
In another preferred construction, the device codes all the unit patterns within a predetermined coding range, classifies all the unit patterns in the range into types according to degrees of matching and sequentially for each type, successively codes and outputs a code indicative of the degree of matching and all of a unit pattern group of a type corresponding to the code.
In another preferred construction, the pattern matching coding device further comprises
a Huffman coding unit, wherein
an identification ID of bit map data in a matching library, the identification flag and registration data are coded and output by the Huffman coding unit.
According to the second aspect of the invention, a method of extracting unit patterns from input binary image data and coding the unit patterns based on a result of sequentially conducted pattern matching with a library pattern, comprising the steps of
storing a first library pattern updatable based on the unit pattern,
comparing the unit pattern with the first library pattern, and
as to a mark pattern determined to be matching, when the number of match error pixels of the pattern is not more than a prescribed value, without coding the bit map, coding an identification ID of a matching bit map in a library and an identification flag indicating that the number of match error pixels is not more than the prescribed value.
In the preferred construction, the coding method further comprising the step of,
when the unit pattern is determined to match the first library pattern, newly registering the unit pattern as the first library pattern.
According to the third aspect of the invention, a method of extracting unit patterns from input binary image data and coding the unit patterns based on a result of sequentially conducted pattern matching with a library pattern, comprising the steps of
storing a first library pattern updatable based on the unit pattern,
storing a second library pattern of a font designated in advance,
comparing the unit pattern with the first library pattern and the second library pattern,
when the unit pattern is determined to match the first library pattern and is not the same as the first library pattern, newly registering the unit pattern as the first library pattern, and
as to a mark pattern determined to be matching, when the number of match error pixels of the pattern is not more than a prescribed value, without coding the bit map, coding an identification ID of a matching bit map in a matching library and an identification flag indicating that the number of match error pixels is not more than the prescribed value.
In the preferred construction, the coding method further comprising the step of,
when the unit pattern is determined to match the first library pattern and is not the same as the first library pattern or when the unit pattern unmatches both the first library pattern and second library pattern, newly registering the unit pattern as the first library pattern.
According to another aspect of the invention, a method of extracting unit patterns from input binary image data and coding the unit patterns based on a result of sequentially conducted pattern matching with a library pattern, comprising the steps of
storing a first library pattern updatable based on the unit pattern,
storing a second library pattern of a font designated in advance,
comparing the unit pattern in a predetermined coding range with the first library pattern and the second library pattern,
when the unit pattern is determined to match the first library pattern and is not the same as the first library pattern, newly registering the unit pattern as the first library pattern,
as to a mark pattern determined to be matching, when the number of match error pixels of the pattern is not more than a prescribed value, correlating an identification ID of a matching library and an identification ID of a bit map of the matching library, and
classifying all the unit patterns in the range into types according to degrees of matching and sequentially for each type, without coding a bit map, successively coding a code indicative of the degree of matching and all of a unit pattern group of a type corresponding to the code.
In the preferred construction, the coding method further comprising the step of,
when the unit pattern is determined to match the first library pattern and is not the same as the first library pattern or when the unit pattern unmatches both the first library pattern and second library pattern, newly registering the unit pattern as the first library pattern.
According to a further aspect of the invention, a computer readable memory which stores a coding program for extracting unit patterns from input binary image data and coding the unit patterns based on a result of sequentially conducted pattern matching with a library pattern, the coding program comprising the steps of
storing a first library pattern updatable based on the unit pattern,
comparing the unit pattern with the first library pattern, and
as to a mark pattern determined to be matching, when the number of match error pixels of the pattern is not more than a prescribed value, without coding the bit map, coding an identification ID of a matching bit map in a library and an identification flag indicating that the number of match error pixels is not more than the prescribed value.
According to a further aspect of the invention, a computer readable memory which stores a coding program for extracting unit patterns from input binary image data and coding the unit patterns based on a result of sequentially conducted pattern matching with a library pattern, wherein the coding program comprises the steps of
storing a first library pattern updatable based on the unit pattern,
storing a second library pattern of a font designated in advance,
comparing the unit pattern with the first library pattern and the second library pattern,
when the unit pattern is determined to match the first library pattern and is not the same as the first library pattern, newly registering the unit pattern as the first library pattern, and
as to a mark pattern determined to be matching, when the number of match error pixels of the pattern is not more than a prescribed value, without coding the bit map, coding an identification ID of a matching bit map in a library and an identification flag indicating that the number of match error pixels is not more than the prescribed value.
According to a further aspect of the invention, a computer readable memory which stores a coding program for extracting unit patterns from input binary image data and coding the unit patterns based on a result of sequentially conducted pattern matching with a library pattern, wherein the coding program comprises the steps of
storing a first library pattern updatable based on the unit pattern,
storing a second library pattern of a font designated in advance,
comparing the unit pattern in a predetermined coding range with the first library pattern and the second library pattern,
when the unit pattern is determined to match the first library pattern and is not the same as the first library pattern, newly registering the unit pattern as the first library pattern,
as to a mark pattern determined to be matching, when the number of match error pixels of the pattern is not more than a prescribed value, correlating an identification ID of a matching library and an identification ID of a bit map of the matching library, and
classifying all the unit patterns in the range into types according to degrees of matching and sequentially for each type, without coding the bit map, successively coding a code indicative of the degree of matching and all of a unit pattern group of a type corresponding to the code.
Other objects, features and advantages of the present invention will become clear from the detailed description given herebelow.
The present invention will be understood more fully from the detailed description given herebelow and from the accompanying drawings of the preferred embodiment of the invention, which, however, should not be taken to be limitative to the invention, but are for explanation and understanding only.